// 另外一种关卡寻路
const int infinity = 999999;
public array find_pass_path(int start_x, int start_y, int goal_x, int goal_y, map ignore_dict = {}, function check_func = nil)
{
    TRACE_INFO("use new pathing .............");
    array pass_list = find_through_pass(start_x, start_y, goal_x, goal_y, check_func);
    if (! pass_list)
        return [];

    return find_path_through_pass(pass_list, start_x, start_y, goal_x, goal_y, ignore_dict);
}

// 搜寻需要通过的关卡点
public array find_through_pass(int start_x, int start_y, int goal_x, int goal_y, function check_func)
{
    // 坐标是否有效
    if (! check_xy(start_x, start_y) || ! check_xy(goal_x, goal_y))
        return nil;

    mixed start_province = find_province_by_xy(start_x, start_y);
    mixed goal_province  = find_province_by_xy(goal_x, goal_y);
    assert(start_province != nil);
    assert(goal_province  != nil);

    // 在同一个行省
    if (start_province == goal_province)
        return [];

    // 目标点在开始行省周围的关卡上
    int pass_id = calc_pos_pass_id(start_province, goal_x, goal_y);
    if (pass_id)
        return [pass_id];

    return dijkstra_pathing(start_x, start_y, start_province, goal_x, goal_y, goal_province, check_func);
}

// dijkstra算法
public array dijkstra_pathing(int start_x, int start_y, mixed start_province, int goal_x, int goal_y, mixed goal_province, function check_func)
{
    map dist = {};
    map scand_dict = {};
    map pass_dict = {};

    // 初始化和start直接相连的行省的距离及需要通过的关卡
    map neighbours = dijkstra_get_neighbours(start_province, goal_x, goal_y, check_func);
    POS start_pos  = grid.new_pos(start_x, start_y);
    for (mixed province_id, array pass_list : neighbours)
    {
        let int distance, int pass_id, POS pass_pos = calc_two_province_distance(start_province, start_pos, province_id, pass_list);
        int extra_distance = calc_goal_province_distance(province_id, pass_pos, goal_province, goal_x, goal_y);
        dist[province_id]  = distance + extra_distance;
        pass_dict[province_id]  = [start_province, pass_id, pass_pos];
    }

    // 自己设置为无穷远
    dist[start_province] = infinity;
    scand_dict[start_province] = true;

    // 循环遍历直到处理完所有邻居，或者找到目标
    while (scand_dict.length() < dist.length())
    {
        // 找出最近的那个行省
        int min_distance   = infinity;
        mixed min_province = 0;
        for (mixed province_id, int distance : dist)
        {
            if (scand_dict[province_id])
                continue;

            if (min_province == 0 || distance < min_distance)
            {
                min_province = province_id;
                min_distance = distance;
            }
        }

        // 所有都处理过了
        if (min_province == 0)
            continue;

        // 找到目标行省了
        if (min_province == goal_province)
            break;

        // 把最近的放入遍历过的列表里
        scand_dict[min_province] = true;

        map neighbours   = dijkstra_get_neighbours(min_province, goal_x, goal_y, check_func);
        POS min_pass_pos = pass_dict[min_province][2];
        for (mixed province_id, array pass_list : neighbours)
        {
            // 如果经过min_province到province_id比直接到province_id还近，更新之
            let int temp, int temp_pass, POS temp_pass_pos = calc_two_province_distance(min_province, min_pass_pos, province_id, pass_list);
            int temp_extra = calc_goal_province_distance(province_id, temp_pass_pos, goal_province, goal_x, goal_y);
            int old = dist[province_id] ?? infinity;
            if (min_distance + temp + temp_extra < old)
            {
                dist[province_id] = min_distance + temp + temp_extra;
                pass_dict[province_id] = [min_province, temp_pass, temp_pass_pos];
            }
        }
    }

    // 从后往前把需要通过的关卡找出来
    array pass_list = [];
    while (true)
    {
        mixed data = pass_dict[goal_province];
        if (! data)
            return nil;

        let mixed next_province, int pass_id = data;
        pass_list.push_back(pass_id);

        if (next_province == start_province)
            break;

        goal_province = next_province;
    }

    return pass_list;
}

// 计算两个行省之间通过哪个关卡最近, 返回距离和需要通过的关卡
array calc_two_province_distance(mixed province1, POS pos, mixed province2, array pass_list)
{
    int min_pass       = 0;
    mixed min_distance = infinity;
    POS min_pass_pos   = nil;
    for (int pass_id : pass_list)
    {
        map pass_pos = get_pass_config(pass_id)["position"];
        int distance = grid.calc_pos_distance(pos, pass_pos);
        if (min_pass == 0 || distance < min_distance)
        {
            min_pass = pass_id;
            min_distance = distance;
            min_pass_pos = pass_pos;
        }
    }
    return [min_distance, min_pass, min_pass_pos];
}

// 如果遍历的行省是目标行省，需要加上后面那一段的距离
int calc_goal_province_distance(mixed province_id, POS pass_pos, mixed goal_province, int goal_x, int goal_y)
{
    if (province_id != goal_province)
        return 0;

    return grid.calc_xy_distance(pass_pos.x, pass_pos.y, goal_x, goal_y);
}

// 根据关卡来寻路
array find_path_through_pass(array pass_list, int start_x, int start_y, int goal_x, int goal_y, map ignore_dict)
{
    // 将所有要通过的关卡加入到忽略点里面，并记录每个关卡点
    array pass_pos_list = [];

     // 将目标点加入到最后一个需要寻路的点
    pass_pos_list.push_back(grid.new_pos(goal_x, goal_y));

    for (int pass_id : pass_list)
    {
        map pass_config = get_pass_config(pass_id);

        map pos_int_dict = pass_config["pos_int_dict"];
        ignore_dict << pos_int_dict;

        POS pass_pos = pass_config["position"];

        // 目标点在关卡上时，前面已经加入了，不再加入
        if (pass_pos.x == goal_x && pass_pos.y == goal_y)
            continue;

        pass_pos_list.push_back(pass_pos);
    }

    // 起始点加入路径中
    array path_list = [];
    path_list.push_back(grid.new_pos(start_x, start_y));

    // 起始位置到关卡的寻路
    int lx = start_x;
    int ly = start_y;
    bool is_succ = true;

    // 关卡点在列表里是反序的，从后向前遍历
    for (int i = pass_pos_list.length() - 1 downto 0)
    {
        POS one_pos = pass_pos_list[i];
        int rx = one_pos["x"];
        int ry = one_pos["y"];

        array relay_path_list = find_path_with_ignore(ignore_dict, lx, ly, rx, ry);
        if (relay_path_list.length() < 1)
        {
            is_succ = false;
            break;
        }

        lx = rx;
        ly = ry;
        path_list.push_back_n(relay_path_list[1..<1]);
    }

    if (! is_succ)
        return [];

    return path_list;
}

// 计算目标点是不是在某个行省周围的关卡上，在返回关卡id，不在返回0
int calc_pos_pass_id(mixed province_id, int goal_x, int goal_y)
{
    int goal_int   = grid.xy_to_int(goal_x, goal_y);
    map neighbours = get_province_passable_neighbours(province_id, nil);
    for (mixed province_id, array pass_list : neighbours)
    {
        for (int pass_id : pass_list)
        {
            map pass_config  = get_pass_config(pass_id);
            map pos_int_dict = pass_config["pos_int_dict"];
            if (pos_int_dict[goal_int])
                return pass_id;
        }
    }

    return 0;
}

// 处理一下往关卡上走的那种情况
map dijkstra_get_neighbours(mixed province_id, int goal_x, int goal_y, function check_func)
{
    map ro_neighbours = get_province_neighbours(province_id);
    if (ro_neighbours == nil)
        return {};

    map neighbours = ro_neighbours.deep_dup();
    for (mixed neighbour_id, array pass_list : neighbours)
    {
        for (int pass_id : pass_list)
        {
            map m = get_pass_config(pass_id);
            if (check_func && ! check_func.call(neighbour_id, pass_id, m))
            {
                // 如果在周围的关卡上，当成可以通行来处理
                if (! calc_pos_pass_id(neighbour_id, goal_x, goal_y))
                    pass_list[__index] = nil;
            }
        }
        pass_list.clean_up();
        if (pass_list.length() < 1)
            neighbours[neighbour_id] = nil;
    }
    return neighbours.clean_up();
}